package practice_2025_9.practice_9_4;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

class Solution {
    /**
     * 前 k 个高频单词
     * @param nums
     * @param k
     * @return
     */
    public int[] topKFrequent(int[] nums, int k) {
        // 计算每个元素出现的频率
        Map<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++) {
            hash.put(nums[i], hash.getOrDefault(nums[i], 0) + 1);
        }
        // 使用 小根堆 存放前 k 个高频元素
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> hash.get(o1) - hash.get(o2));
        int count = 0;
        for(int key: hash.keySet()) {
            if (count < k) {
                queue.add(key);
            } else {
                int tmp = queue.peek();
                if (hash.get(key) > hash.get(tmp)) {
                    queue.poll();
                    queue.add(key);
                }
            }
            count++;
        }
        int[] res = new int[queue.size()];
        int i = 0;
        while(!queue.isEmpty()) {
            res[i++] = queue.poll();
        }
        return res;
    }

    /**
     * 最长连续序列
     * @param nums
     * @return
     */
    public int longestConsecutive(int[] nums) {
        // 连续的最长序列
        // 进行排序
        Arrays.sort(nums);
        int maxLen = 0;
        // 在 hash 中存储 i 位置之前的元素
        int n = nums.length;
        int[] dp = new int[n];
        // 元素 -> 下标
        Map<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < n; i++) {
            int pre = nums[i] - 1;
            dp[i] = hash.getOrDefault(pre, 0) + 1;
            hash.put(nums[i], dp[i]);
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }

// sql 练习: 查询部门工资最高的员工
//    select Department.name as Department , Employee.name as Employee , Employee.salary as Salary
//    from Department, Employee
//    where Department.id = Employee.departmentId
//    and (departmentId, Salary) in
//        (select departmentId, MAX(Salary) from Employee group by departmentId);

}